package com.algorithm.ch1.lzr.array;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 给定两个数组，写一个方法来计算它们的交集
 * 给定 array1 = [1, 2, 2, 1], array2 = [2, 2], 返回 [2, 2]
 *
 * @author lzr
 * @date 2018/8/7
 */
public class Intersect {

    public static void main(String[] args) {
        int[] array1 = {4,7,9,7,6,7};
        int[] array2 = {5,0,0,6,1,6,2,2,4};
        int[] intersect = intersect1(array1, array2);
        for (int i = 0; i < intersect.length; i++) {
            System.out.println(intersect[i]);
        }
        int[] intersect2 = intersect2(array1, array2);
        for (int i = 0; i < intersect2.length; i++) {
            System.out.println(intersect2[i]);
        }

    }

    /**
     * 查找两个数组的交集 先排序再比较
     *
     * @param array1
     * @param array2
     * @return
     */
    public static int[] intersect1(int[] array1, int[] array2) {
        if (array1.length == 0 || array2.length == 0) {
            return new int[]{};
        }
        Arrays.sort(array1);
        Arrays.sort(array2);
        int i = 0;
        int j = 0;
        List<Integer> list = new ArrayList<>();
        while (i < array1.length && j < array2.length) {
            if (array1[i] < array2[j]) {
                i++;
            } else if (array1[i] > array2[j]) {
                j++;
            } else {
                list.add(array1[i]);
                i++;
                j++;
            }
        }
        int[] temp = new int[list.size()];
        for (int k = 0; k < list.size(); k++) {
            temp[k] = list.get(k);
        }
        return temp;
    }


    /**
     * 通过HashMap的方式来实现
     *
     * @param array1
     * @param array2
     * @return
     */
    public static int[] intersect2(int[] array1, int[] array2) {
        if (array1.length == 0 || array2.length == 0) {
            return new int[]{};
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array1.length; i++) {
            if (map.get(array1[i]) != null) {
                Integer count = map.get(array1[i]);
                map.put(array1[i],++count);
            }else{
                map.put(array1[i],1);
            }
        }

        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < array2.length; i++) {
            if (map.get(array2[i]) != null) {
                Integer count = map.get(array2[i]);
                if(count != null && count > 0){
                    map.put(array2[i], --count);
                    list.add(array2[i]);
                }
            }
        }

        int[] temp = new int[list.size()];
        for (int k = 0; k < list.size(); k++) {
            temp[k] = list.get(k);
        }
        return temp;
    }


}
